1. Field of the Invention
The present invention is related to a logic circuit for finding a xe2x80x9c0xe2x80x9d bit or a xe2x80x9c1xe2x80x9d bit by searching a binary bit string. Furthermore, the present invention is related to a carry-lookahead (CLA) circuit for use in arithmetic units handling a number of bits.
2. Prior Art
There are utilized logic circuits called a xe2x80x9c0xe2x80x9d bit searching circuit and a xe2x80x9c1xe2x80x9d bit searching circuit as logic circuits for constituting the hardware of a computer system. The logic circuits of this kind is used to find a xe2x80x9c0xe2x80x9d bit or a xe2x80x9c1xe2x80x9d bit by searching a binary bit string from the most significant bit to the least significant bit. The logic circuits are used to constitute a comparator for determining the largest number among a plurality of numbers, or a priority encoder used in a signal reception circuit having a plurality of input lines and provided, when receiving input signals at two or more input lines, for generating an output signal indicative of the input line receiving an input signal and having the highest priority among from the input lines receiving input signals.
On the other hand, a xe2x80x9c1xe2x80x9d bit searching circuit in accordance with the prior art is composed of a number of the logic gate connected in a matrix form or in a tree arrangement so that the circuit design tends to be complicated. Furthermore, there are a number of gates arranged from the input to the output so that it takes much time to pass input data therethrough.
On the other hand, carry lookahead circuits have been generally utilized in adder circuits for performing the addition operation of an N-bit input signal a less than N-1 greater than , a less than N-2 greater than , . . . , a less than 0 greater than ), referred to simply as a less than N-1:0 greater than , and an N-bit input signal b less than N-1 greater than , b less than N-2 greater than , . . . , b less than 0 greater than , referred to simply as b less than N-1:0 greater than . An example of such a prior art CLA circuit is described in Japanese Patent Published Application No.Hei 3-150630. The prior art carry lookahead circuit as described is a so-called carry select adder which performs the addition operation both in the case that the carry-in signal is xe2x80x9c0xe2x80x9d and in the case that the carry-in signal is xe2x80x9c1xe2x80x9d . In accordance with the carry out from the lower bit operation, either result of the addition operation is selected and output as a correct result.
There is described a carry lookahead circuit as illustrated in FIG. 2 in Japanese Patent Published Application No.Hei 3-150630. Propagate signals P less than 3:0 greater than  and generate signals G less than 3:0 greater than  are calculated during the addition operation of the input signals a less than 3:0 greater than  and the input signals b less than 3:0 greater than  by obtaining the EX-OR and the AND of each corresponding bits of the input signals a less than 3:0 greater than  and the input signals b less than 3:0 greater than . The propagate signals P less than 3:0 greater than  and the generate signals G less than 3:0 greater than  are input to the carry lookahead circuit together with the carry-in signal Cin from the lower stage in order to generate carry signals C less than 3:0 greater than .
FIG. 3 is a block diagram showing an exemplary carry select adder which performs the addition operation both in the case that the carry-in signal is xe2x80x9c0xe2x80x9d and in the case that the carry-in signal is xe2x80x9c1xe2x80x9d and, in accordance with the carry out from the lower bit operation, either result of the addition operation is selected and output as a correct result. The carry lookahead circuit CLA1 serves to performs the addition operation in the case that the carry-in signal is xe2x80x9c1xe2x80x9d while the carry lookahead circuit CLA2 serves to performs the addition operation in the case that the carry-in signal is xe2x80x9c0xe2x80x9d. Either of the outputs of the carry lookahead circuits CLA1 and CLA2 are selected by means of a 2-1 multiplexer MUX.
A bit group 0 is arranged in the form of the 4-bit carry lookahead circuit as illustrated in FIG. 2 in order to handle  less than 0:3 greater than  bits of data having a 32 bit length to be handled- while seven bit groups 1 to 7 are arranged in the form of the 4-bit carry lookahead circuits each designed as illustrated in FIG. 3 in order to handle  less than 4:7 greater than  bits,  less than 8:11 greater than  bits,  less than 12:15 greater than  bits, . . .  less than 28:31 greater than  bits of the data. A carry lookahead circuit capable of handling 32 bits is then formed as illustrated in FIG. 1. C less than 0 greater than  to C less than 3 greater than , C less than 4 greater than  to C less than 7 greater than , C less than 8 greater than  to C less than 11 greater than , . . . , C less than 28 greater than  to C less than 31 greater than  are sequentially generated in this order in the group 0, the group 1, . . . the group 7.
However, there is a following problem in the prior art CLA as described above. FIG. 4 shows the delay time required for completing the calculation, i.e., the delay time required for generating the carry signals C less than 0 greater than  to C less than 31 greater than . Each of the carry lookahead circuits CLA1 and CLA2 of the respective carry lookahead circuits of the group 0 to the group 7 takes the same time T1 required for calculation. However, the multiplexer MUX of the carry lookahead circuit of the group 1 can initiate the operation required for selecting carry signals only after receiving the carry signal C less than 3 greater than  as given from the group 0. The delay time T2 of the multiplexer MUX is accumulated from the group 1 to the group 7 resulting in the total delay time T1+T2*7. Because of this, in accordance with the prior art technique, there is a problem that a longer delay time is required for completing the calculation of carry signals for data having a longer bit sequence.
The present invention has been made in order to solve the shortcomings as described above. It is an object of the present invention to provide logic circuits capable of performing high speed operations with simplified designs.
It is another object of the present invention to provide a carry lookahead circuit wherein it is possible to reduce the delay time required for completing the calculation by obtaining group propagate signals, group generate signals and group kill signals for each m bits by the use of the respective propagate signals, generate signals and kill signals respectively for each of m bits.
In brief, the above and other objects and advantages of the present invention are accomplished by a logic circuit for searching a binary bit string from the most significant bit to the least significant bit for a first xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d bit, said logic circuit comprising:
a NOT gate circuit receiving the most significant bit of said binary bit string and composed of a dynamic logic circuit;
NOR gate circuits provided in a one-to-one correspondence to the respective bits of said binary bit string, each NOR gate circuit receiving the bit of said binary bit string corresponding to the bit position of said each NOR gate circuit and, if any, the bit(s) of said binary bit string which is more significant than the bit corresponding to the bit position of said each NOR gate circuit except for the most significant bit; and
two-input NOR gate circuits each of which receives two logic signals as output from adjacent ones of said NOT and NOR gate circuits.
In accordance with a preferred embodiment of the present invention, said NOT and NOR gate circuits are composed of NMOS FETs connected in parallel between the ground level and the output lines of said NOT and NOR gate circuits.
Also, in accordance with a preferred embodiment of the present invention, a plurality of inverters are provided in advance of said 2-input NOR gate circuits.
In accordance with another aspect of the present invention, a logic circuit comprising:
a dynamic logic circuit composed of a first combinational logic circuit connected between an output line and a ground level, said output line of said dynamic logic circuit being pulled up to a xe2x80x9cHxe2x80x9d level during the precharge period, while said output line is disconnected from said ground level and an electric power source is supplied to said output line, by controlling input signals to the first combinational logic circuit;
said first combinational logic circuit being given input signals to be evaluated during an evaluation period while said output line is disconnected from said electric power source so that said dynamic logic circuit serves to output a logic value corresponding to an logic operation by the use of the input signals;
a pseudo-NMOS circuit composed of a second combinational logic circuit connected between an output line and a ground level, said output line of said pseudo-NMOS circuit being pulled down to a xe2x80x9cLxe2x80x9d level during the precharge period, while said output line is connected to said ground level, by controlling input signals to the first combinational logic circuit;
said second combinational logic circuit being given input signals to be evaluated while an electric power source is supplied to said output line during an evaluation period so that said pseudo-NMOS circuit serves to output a logic value corresponding to an logic operation by the use of the input signals by selectively disconnecting said output line from said ground level; and
a logic gate connected to said dynamic logic circuit and serving to control the supply of the electric power source to said output line of said pseudo-NMOS circuit in accordance with the signal of said output line of said dynamic logic circuit,
wherein said dynamic logic circuit and said pseudo-NMOS circuit are complementary and wherein said logic gate serves to cut off the supply of the electric power source to said output line of said pseudo-NMOS circuit, when said output line of said pseudo-NMOS circuit and said ground level are connected during the evaluation period to pull down said output line to the xe2x80x9cLxe2x80x9d level, in response to the corresponding change of said output line of said dynamic logic circuit.
In accordance with a preferred embodiment of the present invention, said first combinational logic circuit and said second combinational logic circuit have the same arrangement of constituent NMOS FETs.
In accordance with a further aspect of the present invention, a pseudo-NMOS logic circuit comprising:
a first pseudo-NMOS circuit composed of a first combinational logic circuit connected between an output line and a ground level, said output line of said pseudo-NMOS circuit being pulled down to a xe2x80x9cLxe2x80x9d level during the precharge period, while said output line is connected to said ground level, by controlling input signals to the first combinational logic circuit;
said first combinational logic circuit being given input signals to be evaluated while an electric power source is supplied to said output line during an evaluation period so that said first pseudo-NMOS circuit serves to output a logic value corresponding to an logic operation by the use of the input signals by selectively disconnecting said output line from said ground level; and
a second pseudo-NMOS circuit composed of a second combinational logic circuit connected between an output line and a ground level, said output line of said pseudo-NMOS circuit being pulled down to a xe2x80x9cLxe2x80x9d level during the precharge period, while said output line is connected to said ground level, by controlling input signals to the second combinational logic circuit;
said second combinational logic circuit being given input signals to be evaluated while an electric power source is supplied to said output line during an evaluation period so that said second pseudo-NMOS circuit serves to output a logic value corresponding to an logic operation by the use of the input signals by selectively disconnecting said output line from said ground level; and
a first logic gate connected to said second pseudo-NMOS circuit and serving to control the supply of the electric power source to said output line of said first pseudo-NMOS circuit in accordance with the signal of said output line of said second pseudo-NMOS logic circuit,
a second logic gate connected to said first pseudo-NMOS circuit and serving to control the supply of the electric power source to said output line of said second pseudo-NMOS circuit in accordance with the signal of said output line of said first pseudo-NMOS logic circuit,
wherein said first pseudo-NMOS logic circuit and said second pseudo-NMOS logic circuit are complementary and wherein one of said first logic gate and said second logic gate serves to cut off the supply of the electric power source to said output line of one of said first pseudo-NMOS circuit and said second pseudo-NMOS circuit during the evaluation period in response to the corresponding change of said output line of the other of said first pseudo-NMOS circuit and said second pseudo-NMOS circuit to a xe2x80x9cHxe2x80x9d level.
In accordance with a still further aspect of the present invention, a carry lookahead circuit for generating a group propagate signal PG and at least one of a group generate signal GG and a group kill signal KG for a group of m bits (m is an integer no less than 1) by the use of propagate signals P, generate signals G and kill signals K respectively for the constituent bits of the group, said carry lookahead circuit comprising:
a logic circuit for outputting a logic value as said group propagate signal PG and/or the inversion of said logic value as the inversion of said group propagate signal PGB when all of said propagate signals P take said logic value or when all of the inversion of the propagate signals PB take the inversion of said logic value;
a priority encoder for searching said propagate signals P and/or the inversion of said propagate signals PB from the most significant bit to the least significant bit for detecting the inversion of said logic value in said propagate signals P and/or for detecting said logic value in the inversion of said propagate signals PB in order to generate selection signals of m bits one of which is activated corresponding to said propagate signal P detected to take the inversion of said logic value and/or corresponding to the inversion of said propagate signal PB detected to take said logic value
said priority encoder serving to generate said selection signals of which no bit is activated in order to indicate that there is no bit to be selected, when the inversion of said logic value is not detected in said propagate signals P or when said logic value is not detected in the inversion of said propagate signals PB; and
a selector circuit for receiving said selection signals S, selecting one of the generate signals G and/or one of the kill signals K corresponding to the activated bit of said selection signals and outputting said one of the generate signals G and/or said one of the kill signals K as selected as said group generate signal GG and/or said group kill signal KG when there is a bit to be selected of said selection signals,
said selector circuit serving to output the inversion of said logic value as said group generate signal GG and/or said group kill signal KG when there is no bit to be selected of said selection signals.
In accordance with a still further aspect of the present invention, a carry lookahead circuit for generating a group propagate signal PG, a group carry signal CG and at least one of a group generate signal GG and a group kill signal KG for a group of m bits (m is an integer no less than 1) by the use of a carry signal C, propagate signals P, generate signals G and kill signals K respectively for the constituent bits of the group, said carry lookahead circuit comprising:
a logic circuit for outputting a logic value as said group propagate signal PG and/or the inversion of said logic value as the inversion of said group propagate signal PGB when all of said propagate signals P take said logic value or when all of the inversion of the propagate signals PB take the inversion of said logic value;
a priority encoder for searching said propagate signals P and/or the inversion of said propagate signals PB from the most significant bit to the least significant bit for detecting the inversion of said logic value in said propagate signals P and/or for detecting said logic value in the inversion of said propagate signals PB in order to generate selection signals of m bits one of which is activated corresponding to said propagate signal P detected to take the inversion of said logic value and/or corresponding to the inversion of said propagate signal PB detected to take said logic value
said priority encoder serving to generate said selection signals of which no bit is activated in order to indicate that there is no bit to be selected, when the inversion of said logic value is not detected in said propagate signals P or when said logic value is not detected in the inversion of said propagate signals PB; and
a selector circuit for receiving said selection signals S, selecting one of the generate signals G and one of the kill signals K corresponding to the activated bit of said selection signals and outputting said one of the generate signals G and said one of the kill signals K as selected as said group carry signal CG and the inversion of said carry signal CGB when there is a bit to be selected of said selection signals,
said selector circuit serving to output said carry signal C as said group carry signal CG responsive to said group propagate signal PG and the inversion of group propagate signal PGB.
In accordance with a still further aspect of the present invention, a carry lookahead circuit comprising:
a plurality of first carry lookahead circuit groups each of which is composed of a plurality of first carry lookahead circuits;
a second carry lookahead circuit group which is composed of a plurality of second carry lookahead circuits each of which is connected to those of said first carry lookahead circuits belonging to respective one of said first carry lookahead circuit groups; and
a third carry lookahead circuit connected to said second carry lookahead circuits,
wherein each of said first carry lookahead circuits is a carry lookahead circuit for generating a first group propagate signal and at least one of a first group generate signal and a first group kill signal for a group of m bits (m is an integer no less than 1) by the use of propagate signals, generate signals and kill signals respectively for the constituent bits of the group, each of said first carry lookahead circuits comprising:
a logic circuit for outputting a logic value as said first group propagate signal and/or the inversion of said logic value as the inversion of said first group propagate signal when all of said propagate signals take said logic value or when all of the inversion of the propagate signals take the inversion of said logic value;
a priority encoder for searching said propagate signals and/or the inversion of said propagate signals from the most significant bit to the least significant bit for detecting the inversion of said logic value in said propagate signals and/or for detecting said logic value in the inversion of said propagate signals in order to generate selection signals of m bits one of which is activated corresponding to said propagate signal detected to take the inversion of said logic value and/or corresponding to the inversion of said propagate signal detected to take said logic value
said priority encoder serving to generate said selection signals of which no bit is activated in order to indicate that there is no bit to be selected, when the inversion of said logic value is not detected in said propagate signals or when said logic value is not detected in the inversion of said propagate signals: and
a selector circuit for receiving said selection signals S, selecting one of the generate signals and/or one of the kill signals corresponding to the activated bit of said selection signals and outputting said one of the generate signals and/or said one of the kill signals as selected as said first group generate signal and/or said first group kill signal when there is a bit to be selected of said selection signals,
said selector circuit serving to output the inversion of said logic value as said first group generate signal and/or said first group kill signal when there is no bit to be selected of said selection signals,
wherein each of said second carry lookahead circuits is a carry lookahead circuit for generating a second group propagate signal and at least one of a second group generate signal and a second group kill signal for a corresponding first carry lookahead circuit group by the use of said first group propagate signals, said first group generate signals and said first group kill signals respectively output from the constituent carry lookahead circuits of said corresponding first carry lookahead circuit group, each of said second carry lookahead circuits comprising:
a logic circuit for outputting said logic value as said second group propagate signal and/or the inversion of said logic value as the inversion of said second group propagate signal when all of said first group propagate signals take said logic value or when all of the inversion of the first group propagate signals take the inversion of said logic value;
a priority encoder for searching said first group propagate signals and/or the inversion of said first group propagate signals from the most significant bit to the least significant bit for detecting the inversion of said logic value in said first group propagate signals and/or for detecting said logic value in the inversion of said first group propagate signals in order to generate selection signals of a plurality of bits one of which is activated corresponding to said first group propagate signal detected to take the inversion of said logic value and/or corresponding to the inversion of said first group propagate signal detected to take said logic value
said priority encoder serving to generate said selection signals of which no bit is activated in order to indicate that there is no bit to be selected, when the inversion of said logic value is not detected in said first group propagate signals or when said logic value is not detected in the inversion of said first group propagate signals; and
a selector circuit for receiving said selection signals S, selecting one of the first group, generate signals and/or one of the first group kill signals corresponding to the activated bit of said selection signals and outputting said one of the first group generate signals and/or said one of the first group kill signals as selected as said second group generate signal and/or said second group kill signal when there is a bit to be selected of said selection signals,
said selector circuit serving to output the inversion of said logic value as said second group generate signal and/or said second group kill signal when there is no bit to be selected of said selection signals.
wherein each of said third carry lookahead circuits is a carry lookahead circuit for generating a third group propagate signal, a group carry signal and at least one of a third group generate signal and a third group kill signal for a corresponding first carry lookahead circuit group by the use of a carry signal, said second group propagate signals, said second group generate signals and said second group kill signals respectively output from the constituent carry lookahead circuits of said corresponding second carry lookahead circuit group, each of said third carry lookahead circuits comprising:
a logic circuit for outputting a logic value as said third group propagate signal and/or the inversion of said logic value as the inversion of said third group propagate signal when all of said second group propagate signals take said logic value or when all of the inversion of the second group propagate signals take the inversion of said logic value;
a priority encoder for searching said second group propagate signals and/or the inversion of said second group propagate signals from the most significant bit to the least significant bit for detecting the inversion of said logic value in said second group propagate signals and/or for detecting said logic value in the inversion of said second group propagate signals in order to generate selection signals of a plurality of bits one of which is activated corresponding to said second group propagate signal detected to take the inversion of said logic value and/or corresponding to the inversion of said second group propagate signal detected to take said logic value
said priority encoder serving to generate said selection signals of which no bit is activated in order to indicate that there is no bit to be selected, when the inversion of said logic value is not detected in said second group propagate signals or when said logic value is not detected in the inversion of said second group propagate signals; and
a selector circuit for receiving said selection signals S, selecting one of the second group generate signals and one of the second group kill signals corresponding to the activated bit of said selection signals and outputting said one of the second group generate signals and said one of the second group kill signals as selected as said group carry signal and the inversion of said carry signal when there is a bit to be selected of said selection signals,
said selector circuit serving to output said carry signal as said group carry signal responsive to said third group propagate signal and the inversion of said third group propagate signal.